package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 单词搜索 II
 */

public class Code212 {
    public static void main(String[] args) {
        char[][] board = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(new Code212().findWords(board, words));
    }

    class TrieNode {
        Map<Character, TrieNode> children;
        String word;

        public TrieNode() {
            children = new HashMap<>();
            word = null;
        }

        // 删除单词后，如果节点没有子节点且不是单词结尾，可以删除该节点
        public boolean isLeaf() {
            return children.isEmpty();
        }
    }

    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        TrieNode root = buildTrie(words);

        // 遍历每个网格
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }

        return result;
    }

    private void dfs(char[][] board, int row, int col, TrieNode node, List<String> result) {

        // 超出边界、访问过或者不是开头
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
                board[row][col] == '#' || !node.children.containsKey(board[row][col])) {
            return;
        }

        char c = board[row][col];
        TrieNode parent = node;
        TrieNode current = node.children.get(c);

        // 找到单词
        if (current.word != null) {
            result.add(current.word);
            current.word = null; // 避免重复添加
        }

        // 标记访问
        board[row][col] = '#';

        // 搜索四个方向
        for (int[] dir : directions) {
            dfs(board, row + dir[0], col + dir[1], current, result);
        }

        // 回溯
        board[row][col] = c;

        // 优化：如果当前节点是叶子节点，可以从父节点删除
        if (current.isLeaf()) {
            parent.children.remove(c);
        }
    }

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();

        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = word;
        }

        return root;
    }
}
